package com.xiaoyu.linkedArray;

import java.util.Stack;

/**
 * @program: DS_and_A
 * @description: 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *  1.思路1 --> 先入栈,再出栈
 *
 * @author: YuWenYi
 * @create: 2021-04-27 08:59
 **/
public class ReverseList {
    public static ListNode reverseList(ListNode head) {
      //1.入栈法--->运行速度超越百分百,执行空间超越百分之60,很好的一种解决方案
/*      Stack<Integer> nodeNumStack = new Stack<>();
        while (head!=null){   //把链表的数据都放入栈中
            nodeNumStack.push(head.val);
            head = head.next;
        }
        //再通过哨兵结点,来较为方便的获取反转后的链表
        ListNode revList = new ListNode(-1);
        head = revList;   //重复利用head
        while (!nodeNumStack.empty()){
            head.next = new ListNode(nodeNumStack.pop());
            head = head.next;
        }
        return revList.next;*/

     /* 2.递归法求解,比较复杂
       if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;

        1.假设链表是[1, 2, 3, 4, 5]从最底层最后一个reverseList(5)来看
        2.触底,返回了5这个节点
        3.reverseList(4)中
        4.p为5,即指向head.next的地址
        5.head.next.next = head 相当于 5 -> 4
        6.现在节点情况为 4 -> 5 -> 4
        7.head.next = null,切断4 -> 5 这一条，现在只有 5 -> 4
        8.返回（return）p为5，5 -> 4
        9.返回上一层reverseList(3)
        10.处理完后返回的是5 -> 4 -> 3
        11.依次向上
        */

        //解法三:迭代法  -->  头插法改变指针引用
        ListNode newHead = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            //将当前的结点的next指向新的结点
            curr.next = newHead;
            newHead = curr;
            curr = nextTemp;
        }
        return newHead;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1,new ListNode(2,
                new ListNode(3,new ListNode(4,new ListNode(5)))));
        ListNode l2 = new ListNode();

        ListNode res = reverseList(l1);

        while (res.hasNext()){
            System.out.print(res.val+",");
            res = res.next;
        }
        System.out.println(res.val);
    }
}
